/************************************************************************
                                                                     
   Xceed Ultimate ListBox for Silverlight                                                                                                                                            
   Copyright (C) 2010 Xceed Software Inc.    
                                                                     
   This program is provided to you under the terms of the GNU General Public  
   License version 2 as published by the Free Software Foundation. 
        
   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY, without even the implied warranty of 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along 
   with this program, if not, write to the Free Software Foundation, Inc., 
   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

   This program can be provided to you by Xceed Software Inc. under a
   proprietary commercial license agreement for use in non-Open Source
   projects. Visit Xceed.com to find the commercial edition of 
   Xceed Ultimate ListBox for Silverlight.                                    
                                                                      
 **********************************************************************/

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;
using Xceed.Silverlight.Data.Stats;

namespace Xceed.Silverlight.Data
{
  internal class ListDataItemIndex
  {
    #region Constructor

    internal ListDataItemIndex(
      ListDataItemCollection dataSource,
      ListDataItemIndexConfiguration configuration )
    {
      if( dataSource == null )
        throw new ArgumentNullException( "dataSource" );

      if( configuration == null )
        throw new ArgumentNullException( "configuration" );

      m_configuration = configuration;

      IEnumerable<RawDataItem> itemsSource;
      Func<RawDataItem, bool> predicate = configuration.CreatePredicate();
      // Remove the items that must not be part of the index.
      itemsSource = ListDataItemIndex.Filter( dataSource, predicate );
      // Sort the items according to the sort order.
      itemsSource = ListDataItemIndex.Sort( itemsSource, configuration.SortOrder );
      m_dataSource = itemsSource.ToList();

      IEqualityComparer<StatFunction> statFunctionComparer = new StatFunctionEqualityComparer();
      m_root = ListDataItemIndex.CreateIndex( m_dataSource, configuration, statFunctionComparer );
    }

    #endregion

    #region Configuration Property

    internal ListDataItemIndexConfiguration Configuration
    {
      get
      {
        return m_configuration;
      }
    }

    private ListDataItemIndexConfiguration m_configuration;

    #endregion

    #region ItemsCount Property

    internal int ItemsCount
    {
      get
      {
        return m_dataSource.Count;
      }
    }

    #endregion

    internal void Add( RawDataItem dataItem )
    {
      if( dataItem == null )
        return;

      // Make sure the data item should be added to the index.
      Func<RawDataItem, bool> predicate = m_configuration.CreatePredicate();
      if( ( predicate != null ) && ( !predicate.Invoke( dataItem ) ) )
        return;

      int index = m_dataSource.BinarySearch( dataItem, m_configuration.ItemComparer );
      if( index < 0 )
      {
        index = ~index;
      }

      m_dataSource.Insert( index, dataItem );

      // Repair the the tree.
      if( m_root != null )
      {
        IEnumerable<object> groupValues = ( from sort in m_configuration.SortOrder
                                            select dataItem.GetDataMemberValue( sort.PropertyName ) );
        LinkedList<object> groupValue = new LinkedList<object>( groupValues );

        m_root.Add( groupValue.First );
      }
      // We only have one item in the index.
      else
      {
        IEqualityComparer<StatFunction> statFunctionComparer = new StatFunctionEqualityComparer();
        m_root = ListDataItemIndex.CreateIndex(
                   m_dataSource,
                   m_configuration,
                   statFunctionComparer );
      }

      // Any enumerable on the index should be discarded.
      m_version++;
    }

    internal void Remove( RawDataItem dataItem )
    {
      if( dataItem == null )
        return;

      // We must check if the item is in the index even if it doesn't pass the configuration 
      // filter predicate right now since a property change may have occured.
      int index = m_dataSource.BinarySearch( dataItem, m_configuration.ItemComparer );
      if( index < 0 )
      {
        // The item may not be sorted anymore if it has changed.
        // We must look for it item by item.
        index = m_dataSource.IndexOf( dataItem );

        // The item doesn't seem to be in the data source at all.
        if( index < 0 )
          return;
      }

      m_dataSource.RemoveAt( index );

      Debug.Assert( m_root != null );

      // We must remove the root node if there is no more item in the collection.
      if( m_root.Remove( index ) )
      {
        m_root = null;
      }

      // Any enumerable on the index should be discarded.
      m_version++;
    }

    internal ListDataItemEnumerable GetDataItems( bool reverseOrder )
    {
      // Determine the desired range.
      int startIndex = 0;
      int length = m_dataSource.Count;
      int totalCount = length;

      if( reverseOrder )
      {
        startIndex = length - 1;
        length = -length;
      }

      // Retrieve an enumerator on the desired items.
      IEnumerable<RawDataItem> dataItems = this.GetDataItems( startIndex, length );

      return new ListDataItemEnumerable( dataItems, totalCount, totalCount );
    }

    internal ListDataItemEnumerable GetDataItems(
      IEnumerable<object> startingValues,
      bool reverseOrder )
    {
      return this.GetDataItems( startingValues, reverseOrder, false );
    }

    internal ListDataItemEnumerable GetDataItems(
      IEnumerable<object> startingValues,
      bool reverseOrder,
      bool skipStartingItem )
    {
      if( m_root == null )
        return ListDataItemEnumerable.Empty();

      if( !startingValues.Any() )
        return this.GetDataItems( reverseOrder );

      LinkedList<object> groupValues = new LinkedList<object>( startingValues );

      // Get the index of the first item to return.
      int startIndex = m_root.GetDataItemIndex( groupValues.First, reverseOrder, skipStartingItem );
      int totalCount = m_dataSource.Count;

      // We are out of bound, there is no item to return.
      if( ( startIndex < 0 ) || ( startIndex >= totalCount ) )
        return ListDataItemEnumerable.Empty( totalCount );

      int length = ( reverseOrder )
                     ? -( startIndex + 1 )
                     : totalCount - startIndex;

      // Retrieve an enumerator on the desired range.
      IEnumerable<RawDataItem> dataItems = this.GetDataItems( startIndex, length );

      return new ListDataItemEnumerable( dataItems, Math.Abs( length ), totalCount );
    }

    internal IEnumerable<int> GetGroupCount( int levelCount )
    {
      if( levelCount < 0 )
        throw new ArgumentOutOfRangeException( "levelCount", "levelCount must be greater than or equal to zero." );

      LinkedList<int> groupCount = new LinkedList<int>( Enumerable.Repeat( 0, levelCount ) );
      if( m_root != null )
      {
        m_root.GetGroupCount( groupCount.First );
      }

      return groupCount;
    }

    internal IEnumerable<int> GetGroupCount(
      int levelCount,
      IEnumerable<object> startingValues )
    {
      if( levelCount < 0 )
        throw new ArgumentOutOfRangeException( "levelCount", "levelCount must be greater than or equal to zero." );

      LinkedList<int> groupCount = new LinkedList<int>( Enumerable.Repeat( 0, levelCount ) );
      if( m_root != null )
      {
        LinkedList<object> groupValues = new LinkedList<object>( startingValues );
        m_root.GetGroupCount( groupCount.First, groupValues.First );
      }

      return groupCount;
    }

    internal IEnumerable<int> GetGroupCount(
      int levelCount,
      IEnumerable<object> startingValues,
      bool reverseOrder )
    {
      return this.GetGroupCount( levelCount, startingValues, reverseOrder, false );
    }

    internal IEnumerable<int> GetGroupCount(
      int levelCount,
      IEnumerable<object> startingValues,
      bool reverseOrder,
      bool skipStartingItem )
    {
      if( levelCount < 0 )
        throw new ArgumentOutOfRangeException( "levelCount", "levelCount must be greater than or equal to zero." );

      LinkedList<int> groupCount = new LinkedList<int>( Enumerable.Repeat( 0, levelCount ) );
      if( m_root != null )
      {
        LinkedList<object> groupValues = new LinkedList<object>( startingValues );
        m_root.GetGroupCount( groupCount.First, groupValues.First, reverseOrder, skipStartingItem );
      }

      return groupCount;
    }

    internal IEnumerable<int> GetGroupCount(
      int levelCount,
      IEnumerable<object> groupValues,
      IEnumerable<object> startingValues,
      bool reverseOrder,
      bool skipStartingItem )
    {
      if( levelCount < 0 )
        throw new ArgumentOutOfRangeException( "levelCount", "levelCount must be greater than or equal to zero." );

      LinkedList<int> groupCount = new LinkedList<int>( Enumerable.Repeat( 0, levelCount ) );
      if( m_root != null )
      {
        LinkedList<object> filterGroupValues = new LinkedList<object>( groupValues );
        LinkedList<object> groupStartingValues = new LinkedList<object>( startingValues );

        m_root.GetGroupCount(
          groupCount.First,
          filterGroupValues.First,
          groupStartingValues.First,
          reverseOrder,
          skipStartingItem );
      }

      return groupCount;
    }

    internal void ClearStatResults()
    {
      if( m_root != null )
      {
        m_root.ClearStatResults();
      }
    }

    internal StatResult GetStatValue( 
      StatFunction statFunction, 
      IEnumerable<object> groupValues )
    {
      if( ( m_root == null ) || ( statFunction == null ) )
        return null;

      LinkedListNode<object> firstGroupValue = null;

      if( ( groupValues != null ) && ( groupValues.Any() ) )
        firstGroupValue = ( new LinkedList<object>( groupValues ) ).First;

      return m_root.GetStatValue( statFunction, firstGroupValue );
    }

    internal void SetStatValue(
      StatFunction statFunction,
      IEnumerable<object> groupValues,
      StatResult statResult )
    {
      if( ( m_root == null ) || ( statFunction == null ) )
        return;

      LinkedListNode<object> firstGroupValue = null;

      if( ( groupValues != null ) && ( groupValues.Any() ) )
        firstGroupValue = ( new LinkedList<object>( groupValues ) ).First;

      m_root.SetStatValue( statFunction, firstGroupValue, statResult );
    }

    private IEnumerable<RawDataItem> GetDataItems( int startIndex, int length )
    {
      return this.GetDataItems( startIndex, length, m_version );
    }

    private IEnumerable<RawDataItem> GetDataItems( int startIndex, int length, int version )
    {
      if( length == 0 )
        yield break;

      int index = startIndex;
      int step = Math.Sign( length );
      int count = Math.Abs( length );

      while( true )
      {
        // Make sure the data list has changed since the last enumerated value.
        if( version != m_version )
          throw new InvalidOperationException( "An attempt was made to retrieve the data items from a data source that has changed." );

        // We've enumerable all the desired values or the end of the source has been reached.
        if( ( count <= 0 ) || ( index < 0 ) || ( index >= m_dataSource.Count ) )
          yield break;

        // Return the desired item.
        yield return m_dataSource[ index ];

        index += step;
        count--;
      }
    }

    private static Func<LinkedListNode<object>, int, ListDataItemIndexNode> GetBranchCreator(
      List<RawDataItem> dataSource,
      ListDataItemIndexConfiguration configuration,
      IEqualityComparer<StatFunction> statFunctionComparer )
    {
      int levelCount = configuration.SortOrder.Count;

      Func<LinkedListNode<object>, int, ListDataItemIndexNode> branchCreator = null;
      branchCreator =
        ( groupValues, indexStart ) =>
        {
          // Find out at which level we are now.
          int level = levelCount;
          LinkedListNode<object> levelValue = groupValues;
          while( levelValue != null )
          {
            level--;
            levelValue = levelValue.Next;
          }

          // We are on the last level.
          if( level >= configuration.SortOrder.Count - 1 )
            return new ListDataItemIndexLeaf( configuration, statFunctionComparer, level, indexStart, 1, dataSource.BinarySearch );

          ListDataItemIndexNode childContainer = branchCreator.Invoke( groupValues.Next, indexStart );
          ListDataItemIndexGroup childGroup = new ListDataItemIndexGroup( groupValues.Value, childContainer );

          return new ListDataItemIndexGroupContainer(
            configuration,
            statFunctionComparer,
            level,
            indexStart,
            1,
            new ListDataItemIndexGroup[] { childGroup },
            branchCreator );
        };

      return branchCreator;
    }

    private static ListDataItemIndexNode CreateIndex(
      List<RawDataItem> dataSource,
      ListDataItemIndexConfiguration configuration,
      IEqualityComparer<StatFunction> statFunctionComparer )
    {
      // There is no index to create if there is no data.
      if( dataSource.Count <= 0 )
        return null;

      Func<LinkedListNode<object>, int, ListDataItemIndexNode> branchCreator = ListDataItemIndex.GetBranchCreator(
                                                                                 dataSource,
                                                                                 configuration,
                                                                                 statFunctionComparer );

      return ListDataItemIndex.CreateLevel(
        dataSource,
        configuration,
        statFunctionComparer,
        0,
        0,
        dataSource.Count,
        branchCreator );
    }

    private static ListDataItemIndexNode CreateLevel(
      List<RawDataItem> dataSource,
      ListDataItemIndexConfiguration configuration,
      IEqualityComparer<StatFunction> statFunctionComparer,
      int level,
      int startIndex,
      int length,
      Func<LinkedListNode<object>, int, ListDataItemIndexNode> branchCreator )
    {
      // We are on the leaf level.
      if( level >= configuration.SortOrder.Count - 1 )
        return new ListDataItemIndexLeaf( 
                 configuration, 
                 statFunctionComparer, 
                 level, 
                 startIndex, 
                 length, 
                 dataSource.BinarySearch );

      string memberName = configuration.SortOrder[ level ].PropertyName;
      List<ListDataItemIndexGroup> childGroups = new List<ListDataItemIndexGroup>();

      // Regroup the items that share the same group value.
      int endIndex = Math.Min( startIndex + length, dataSource.Count );
      int i = startIndex;
      while( i < endIndex )
      {
        object groupValue = dataSource[ i ].GetDataMemberValue( memberName );
        int groupLength = 0;

        // Find out the number of items that are part of the same group.
        for( int j = i; j < endIndex; j++ )
        {
          // Check if a new group has begun.
          if( !object.Equals( dataSource[ j ].GetDataMemberValue( memberName ), groupValue ) )
            break;

          groupLength++;
        }

        // Create the children groups.
        ListDataItemIndexNode childContainer = ListDataItemIndex.CreateLevel(
                                                 dataSource,
                                                 configuration,
                                                 statFunctionComparer,
                                                 level + 1,
                                                 i,
                                                 groupLength,
                                                 branchCreator );
        if( childContainer != null )
        {
          ListDataItemIndexGroup childGroup = new ListDataItemIndexGroup( groupValue, childContainer );
          childGroups.Add( childGroup );
        }

        i += groupLength;
      }

      // Create the main container.
      return new ListDataItemIndexGroupContainer(
        configuration,
        statFunctionComparer,
        level,
        startIndex,
        length,
        childGroups,
        branchCreator );
    }

    private static IEnumerable<TElement> Filter<TElement>(
      IEnumerable<TElement> source,
      Func<TElement, bool> predicate )
    {
      if( predicate == null )
        return source;

      return source.Where( predicate );
    }

    private static IEnumerable<TElement> Sort<TElement>(
      IEnumerable<TElement> source,
      IEnumerable<SortDescription> sortOrder ) where TElement : RawDataItem
    {
      if( !sortOrder.Any() )
        return source;

      bool isFirstDescription = true;
      IOrderedEnumerable<TElement> result = null;

      foreach( SortDescription sort in sortOrder )
      {
        string memberName = sort.PropertyName;
        bool isAscending = ( sort.Direction == ListSortDirection.Ascending );

        Func<TElement, object> keySelector = ( TElement item ) =>
        {
          return item.GetDataMemberValue( memberName );
        };

        if( isFirstDescription )
        {
          isFirstDescription = false;
          result = ( isAscending )
                     ? source.OrderBy( keySelector )
                     : source.OrderByDescending( keySelector );
        }
        else
        {
          result = ( isAscending )
                     ? result.ThenBy( keySelector )
                     : result.ThenByDescending( keySelector );
        }
      }

      return result;
    }

    #region Private Fields

    private ListDataItemIndexNode m_root; //null
    private List<RawDataItem> m_dataSource; //null
    private int m_version; //0

    #endregion

    #region Private StatFunctionEqualityComparer Nested Type

    private class StatFunctionEqualityComparer : IEqualityComparer<StatFunction>
    {
      public int GetHashCode( StatFunction obj )
      {
        if( obj == null )
          return 0;

        return obj.GetEquivalenceKey();
      }

      public bool Equals( StatFunction x, StatFunction y )
      {
        return StatFunction.AreEquivalents( x, y );
      }
    }

    #endregion
  }
}
